package com.chj.dfs.class04;

import java.util.ArrayDeque;
import java.util.Deque;

public class Code20_CourseSchedule {
	public static class GraphNode {
		public int label;
		public GraphNode[] neighbors;

		public GraphNode(int x) {
			this.label = x;
			neighbors = new GraphNode[10000];
		}
	}

	public static boolean canFinish(int numCourses, int[][] prerequisites) {
		GraphNode[] graph = new GraphNode[10000];
		// 存储入度
		int[] degree = new int[10000];

		Deque<GraphNode> Q = new ArrayDeque<GraphNode>();

		// 初始化邻接表，初始化入度的值为0
		for (int i = 0; i < numCourses; i++) {
			graph[i] = new GraphNode(i);
			degree[i] = 0;
		}

		// 创建图，链接图的顶点
		for (int i = 0; i < prerequisites.length; i++) {
			GraphNode begin = graph[prerequisites[i][1]];
			GraphNode end = graph[prerequisites[i][0]];
			// 使得课程2指向课程1
			begin.neighbors[i] = end;
			// 课程1的入度++
			degree[prerequisites[i][0]]++;
		}

		// 初始化队列中的元素
		for (int i = 0; i < numCourses; i++) {
			if (degree[i] == 0) {
				Q.addFirst(graph[i]);
			}
		}

		// 宽搜
		while (!Q.isEmpty()) {
			GraphNode node = Q.pollFirst();

			// 把队列中元素所指的每个节点的入度减1
			for (int i = 0; i < node.neighbors.length; i++) {

				if (node.neighbors[i] != null) {
					degree[node.neighbors[i].label]--;

					// 将入度为0的节点加入队列中
					if (degree[node.neighbors[i].label] == 0) {
						Q.addFirst(node.neighbors[i]);
					}
				}
			}
		}

		// 存在入度不为0的节点，说明有环
		for (int i = 0; i < numCourses; i++) {
			if (degree[i] != 0) {
				return false;
			}
		}

		return true;
	}

	public static void main(String[] args) {
		int numCourses = 4;
		int[][] prerequisites = new int[][] { { 1, 0 }, { 2, 0 }, { 3, 1 }, { 3, 2 } };
		System.out.println(canFinish(numCourses, prerequisites));
	}
}
